"""
桶排序：
    最坏复杂度: 时间复杂度为 O(n+k)
    最好复杂度：时间复杂度在 O(n)
基本思想：
    设置一个定量的数组当作空桶；
    遍历输入数据，并且把数据一个一个放到对应的桶里去；
    对每个不是空的桶进行排序；
    从不是空的桶里把排好序的数据拼接起来
"""
import math
import random
from insertionSort import insertion_sort
DEFAULT_BUCKET_SIZE = 5


def bucket_sort(sequence, bucketSize=DEFAULT_BUCKET_SIZE):
    if len(sequence) == 0:
        return []
    min_value = sequence[0]
    max_value = sequence[0]
    for i in range(0, len(sequence)):
        if sequence[i] < min_value:
            min_value = sequence[i]   # 寻找最小值
        elif sequence[i] > max_value:
            max_value = sequence[i]   # 最大值
    bucket_count = math.floor((max_value - min_value) / bucketSize) + 1
    buckets = []
    for i in range(0, bucket_count):
        buckets.append([])
    for i in range(0, len(sequence)):
        # 遍历数据，将数据依次放进桶中
        buckets[math.floor((sequence[i] - min_value) / bucketSize)].append(sequence[i])

    sorted_arr = []
    # 每一个非空桶都进行排序
    for i in range(0, len(buckets)):
        insertion_sort(buckets[i])
        for j in range(0, len(buckets[i])):
            sorted_arr.append(buckets[i][j])
    return sorted_arr


if __name__ == '__main__':
    sequence = [random.randint(1, 10000) for i in range(50)]
    print(sequence)
    print(bucket_sort(sequence))

